package com.ryujung.hash.leetCode_15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    /**
     * 数组中任意三个数字，要求其和为0.
     * <p>
     * ++-,--+,000,+0-
     * <p>
     * 减少重复遍历和判断是这道题的关键
     * <p>
     * 思路：
     * 排序 + 双指针
     * <p>
     * 将数组排序，进行遍历，
     * 同时定义两个指针，指向 i 右侧的值 left 和数组尾部的值 right
     * 根据 nums[i]+nums[left]+nums[right]的大小，移动指针
     * 将符合题意的结果放入结果集，同时注意去重，要跳过相同的值
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 最左侧的值必须为负数或0
            if (nums[i] > 0) {
                break;
            }
            int l = i + 1;
            int r = nums.length - 1;
            // -4,-1,-1,0,1,2
            while (l < r) {
                // 最右侧的数必须为非负数
                if (nums[r] < 0) break;

                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    // 跳过相同的值，要注意不能角标越界，否则会出异常
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                    while (r > l && nums[r] == nums[r + 1]) {
                        r--;
                    }
                } else if (sum > 0) { // nums[r]太大，继续左移
                    r--;
                } else { // sum <0 ，nums[l]太小，继续右移
                    l++;
                }
            }
        }
        return res;
    }

}